
#ifndef COMMUNITY_H
#define COMMUNITY_H

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <map>

#if defined(_WIN32)  || defined(WIN32)  || defined(__WIN32__) || defined(_WIN64)  || defined(WIN64) || defined(__WIN64__) || defined(_WINDOWS) || defined(__WINDOWS__)
#define __WIN__
#endif

#ifdef __WIN__ 
#include <windows.h>
#endif

#include "graph_binary.h"

using namespace std;

class Community {
public:
	vector<double> neigh_weight;
	vector<unsigned int> neigh_pos;
	unsigned int neigh_last;

	// network to compute communities for
	Graph g;

	// nummber of nodes in the network and size of all vectors
	int size;

	// community to which each node belongs
	vector<int> n2c;

	// used to compute the modularity participation of each community
	vector<double> in, tot;

	// number of pass for one level computation
	// if -1, compute as many pass as needed to increase modularity
	int nb_pass;

	// a new pass is computed if the last one has generated an increase
	// greater than min_modularity
	// if 0. even a minor increase is enough to go for one more pass
	double min_modularity;

	// Markov Time
	double time;

	// constructors:
	// reads graph from file using graph constructor
	// type defined the weighted/unweighted status of the graph file
	Community(char *filename, char *filename_w, int type, int nb_pass,
			double min_modularity);

	Community(double * data, int length_data, int nbp, double minm,
			double timet, int type);

	// copy graph
	Community(Graph g, int nb_pass, double min_modularity, double timet);

	~Community();

	// display the community of each node
	void display();

	// remove the node from its current community with which it has dnodecomm links
	inline void remove(int node, int comm, double dnodecomm);

	// insert the node in comm with which it shares dnodecomm links
	inline void insert(int node, int comm, double dnodecomm);

	// compute the gain of modularity if node where inserted in comm
	// given that node has dnodecomm links to comm.  The formula is:
	// [(In(comm)+2d(node,comm))/2m - ((tot(comm)+deg(node))/2m)^2]-
	// [In(comm)/2m - (tot(comm)/2m)^2 - (deg(node)/2m)^2]
	// where In(comm)    = number of half-links strictly inside comm
	//       Tot(comm)   = number of half-links inside or outside comm (sum(degrees))
	//       d(node,com) = number of links from node to comm
	//       deg(node)   = node degree
	//       m           = number of links
	inline double modularity_gain(int node, int comm, double dnodecomm,
			double w_degree);

	// compute the set of neighboring communities of node
	// for each community, gives the number of links from node to comm
	void neigh_comm(unsigned int node);

	// compute the modularity of the current partition
	double modularity();

	// displays the graph of communities as computed by one_level
	void partition2graph();
	// displays the current partition (with communities renumbered from 0 to k-1)
	void display_partition(char *outfilename);
	vector<vector<int> > display_partition2(vector<vector<int> > output);

	// generates the binary graph of communities as computed by one_level
	Graph partition2graph_binary();

	// compute communities of the graph for one level
	// return true if some nodes have been moved
	bool one_level();
};

inline void Community::remove(int node, int comm, double dnodecomm) {
	assert(node >= 0 && node < size);

	tot[comm] -= g.weighted_degree(node);
	in[comm] -= 2 * dnodecomm + g.nb_selfloops(node);
	n2c[node] = -1;
}

inline void Community::insert(int node, int comm, double dnodecomm) {
	assert(node >= 0 && node < size);

	tot[comm] += g.weighted_degree(node);
	in[comm] += 2 * dnodecomm + g.nb_selfloops(node);
	n2c[node] = comm;
}

inline double Community::modularity_gain(int node, int comm, double dnodecomm,
		double w_degree) {
	assert(node >= 0 && node < size);

	double totc = (double) tot[comm];
	double degc = (double) w_degree;
	double m2 = (double) g.total_weight;
	double dnc = (double) dnodecomm;

	return (time * dnc - totc * degc / m2);
}

#endif // COMMUNITY_H
